package algorithm.sort.nlogn;

import algorithm.sort.n2.HelperTest;
import algorithm.sort.n2.InsertionSort;

import java.util.Arrays;

/**
 * @author: Oliver
 * @time: 2020/5/31/20:12
 * 归并排序  将数组进行二分，然后进行归并， 从大到小排序
 * 在归并的过程中进行排序，需要借助一个额外的数组进行存放当前需要进行归并的元素，使得k指向下一个将要归并的位置，
 * i左边数组的真要进行比较的元素
 * j右边数组将要比较的元素
 * mid两个数组的中间点
 * 归并排序 强调如何去归并。
 */
public class MergeSort {
    // 测试MergeSort
    public static void main(String[] args) {

        // Merge Sort是我们学习的第一个O(nlogn)复杂度的算法
        // 可以在1秒之内轻松处理100万数量级的数据
        // 注意：不要轻易尝试使用SelectionSort, InsertionSort或者BubbleSort处理100万级的数据
        // 否则，你就见识了O(n^2)的算法和O(nlogn)算法的本质差异：）
        Integer[] arr = {12, 3, 4, 1, 15, 16, 8, 23};
        sort(arr);
        HelperTest.printArray(arr);
        return;
    }

    public static void sort(Comparable[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    /**
     * 递归使用归并排序,对arr[l...r]的范围进行排序
     *
     * @param arr
     * @param l
     * @param n
     */
    private static void sort(Comparable[] arr, int l, int n) {
        //递归终止条件--当只有一个元素或者一个元素都没有的时候
//        if (l >= n) {
//            return;
//        }
        // 优化2: 对于小规模数组, 使用插入排序
        if (n - l <= 15) {
            InsertionSort.sortIndex(arr, l, n);
            return;
        }
        // 计算中间值
        int mid = l + (n - l) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, n);
        //递归从下一层退出到上一层时，进行merge操作
        if (arr[mid].compareTo(arr[mid + 1]) < 0)
            merge(arr, mid, l, n);
    }

    /**
     * 将arr[l...mid]和arr[mid+1...r]两部分进行归并
     *
     * @param arr
     * @param mid
     * @param l
     * @param r
     */
    private static void merge(Comparable[] arr, int mid, int l, int r) {
        // 开辟一个空间存放当前需要归并的元素  copyOfRange 这个应该是前闭后开的复制，所以需要+1
        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);
        // i 左边部分正要处理的元素，j有半部分正要处理的元素 k下一个存放元素的位置
        //arr[i,mid]  arr[mid+1,j] 满足定义  k指向当前需要比较的元素 初始值情况： k=l
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {
            //存在i j越界情况，也就是说左边或者右边元素已经存放完，但是另一边元素还没有安置，这时候需要将另一边元素全部进行安置
            //左边部分处理完毕
            if (i > mid) {
                arr[k] = aux[j - l];
                j++;
            }//右边部分处理完毕
            else if (j > r) {
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l].compareTo(aux[j - l]) > 0) {
                //比较左右两个部分那个元素大，将大的进行安置
                arr[k] = aux[i - l];
                i++;
            } else {
                arr[k] = aux[j - l];
                j++;
            }
        }
    }

    /**
     * 自底向上的排序
     *
     * @param arr
     */
    public void sortBU(Comparable[] arr) {
        int n = arr.length;
        // Merge Sort Bottom Up 优化
        // 对于小数组, 使用插入排序优化
        for (int i = 0; i < n; i += 16)
            InsertionSort.sortIndex(arr, i, Math.min(i + 15, n - 1));

        for (int sz = 16; sz < n; sz += sz)
            for (int i = 0; i < n - sz; i += sz + sz)
                // 对于arr[mid] <= arr[mid+1]的情况,不进行merge
                if (arr[i + sz - 1].compareTo(arr[i + sz]) > 0)
                    merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1));
    }
}
